# coding=utf-8
__author__ = 'st316'
'''
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
'''


class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        return self.isMatchX(s, self.preSimplify(p), 0, 0)

    def isMatchX(self, s, p, i, j):
        # if s == 'aaaaaaaaaaaaab':
        #     return False
        if j == len(p):  # 如果P已经走完，那么S是否匹配成功取决于S是否走完
            return i == len(s)
            # if len(p) - j == 1:
        #     return len(s) - i == 1 and (p[j] == '.' or p[j] == s[i])
        if j + 1 > len(p) - 1 or p[j + 1] != '*':  # next char is not '*': must match current character
            return i < len(s) and (p[j] == s[i] or p[j] == '.') and self.isMatchX(s, p, i + 1, j + 1)

        while i < len(s) and (p[j] == s[i] or p[j] == '.'):  # next char is '*'
            if self.isMatchX(s, p, i, j + 2):
                return True
            i += 1
        return self.isMatchX(s, p, i, j + 2)

    def preSimplify(self, p):  # 简单的对P进行简化去除多余的 c*，如c*c*可以简化为c*
        if len(p) < 5:
            return p
        else:
            i = len(p) - 1
            while i > 3:
                if p[i] == '*' and p[i - 2] == '*' and p[i - 1] == p[i - 3]:
                    p = p[:i - 1] + p[i + 1:]
                    i -= 2
                else:
                    i -= 1
            return p


if __name__ == '__main__':
    s = Solution()
    #from time import clock

    #start = clock()
    print s.isMatch('aaaaaaaaaaaaab', 'a*a*a*a*a*a*a*a*a*a*c')
    #finish = clock()
    #print (finish - start)
